翻訳と辞書 Words near each other ・ Squash at the World Games 2005 – women's singles ・ Squash at the World Games 2009 – men's singles ・ Squash at the World Games 2009 – women's singles ・ Squash at the World Games 2013 ・ Square wave ・ Square wheel ・ Square Window ・ Square yard ・ Square Yards ・ Square – Brussels Meeting Centre ・ Square's Tom Sawyer ・ Square, Inc. ・ Square-cube law ・ Square-free element ・ Square-free integer ・ Square-free polynomial ・ Square-free word ・ Square-inch analysis ・ Square-integrable function ・ Square-lattice Ising model ・ Square-Point ・ Square-rigged caravel ・ Square-spot rustic ・ Square-summable ・ Square-tailed bulbul ・ Square-tailed drongo ・ Square-tailed drongo-cuckoo ・ Square-tailed kite ・ Square-tailed nightjar ・ Square-tailed saw-wing Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Square-free polynomial ： ウィキペディア英語版 Square-free polynomial In mathematics, a square-free polynomial is a polynomial defined over a field or, more generally, a unique factorization domain that is not a multiple of the square of a non unit factor. In the important case of univariate polynomials over a field ''k'', this means that, $f\; \backslash in\; k()$ is square-free if and only if $b^2\; \backslash nmid\; f$ for every polynomial $b\; \backslash in\; k()$ of positive degree.〔Yun, David Y.Y. (1976). (On square-free decomposition algorithms ) ''SYMSAC '76 Proceedings of the third ACM symposium on Symbolic and algebraic computation'', p. 26-35.〕 In applications in physics and engineering, a square-free polynomial is commonly called a polynomial with no repeated roots (such polynomials are called separable, but over a perfect field that is the same as square-free). A square-free decomposition or square-free factorization of a polynomial is a factorization into powers of square-free factors :$$ f = a_1 a_2^2 a_3^3 \cdots a_n^n \, where the ''a''''k'' that are not equal to 1 are pairwise coprime square-free polynomials.〔 Every non-zero polynomial with coefficients in a field admits a square-free factorization, which is unique up to the multiplication of the factors by non zero constants. The square-free factorization is much easier to compute than the complete factorization into irreducible factors, and is thus often preferred when the complete factorization is not really needed, like for the partial fraction decomposition and the symbolic integration of rational fractions. Square-free factorization is the first step of the polynomial factorization algorithms which are implemented in computer algebra systems. Therefore, the algorithm of square-free factorization is basic in computer algebra. In the case of univariate polynomials over a field, any multiple factor of a polynomial introduces a nontrivial common factor of ''f'' and its formal derivative ''f'' ′, so a sufficient condition for ''f'' to be square-free is that the greatest common divisor of ''f'' and ''f'' ′ is 1. Over a perfect field, all irreducible polynomials are separable, so that condition is also necessary. If the polynomial is not square free, the product of the $a\_i$ in the above square free decomposition may be obtained as the quotient of $f$ by its GCD with its derivative. Further GCD computations and exact divisions allow to compute the square-free factorization (see square-free factorization over a finite field). In characteristic zero, a better algorithm is known, Yun's algorithm, which is described below.〔 Its computational complexity is, at most, twice that of the GCD computation of the input polynomial and its derivative. More precisely, if $T\_$ is the time needed to compute the GCD of two polynomials of degree $n$ and the quotient of these polynomial by the GCD, then $2T\_$ is an upper bound for the time needed to compute the square free decomposition. There are also known algorithms for the computation of the square-free decomposition of multivariate polynomials.〔Gianni P., Trager B. (1996). (Square-Free Algorithms in Positive Characteristic ) ''Applicable Algebra In Engineering, Communication And Computing'', 7(1), p. 1-14.〕 ==Yun's algorithm== In this section we describe Yun's algorithm for the square-free decomposition of univariate polynomials over a field of characteristic 0.〔 It proceeds by a succession of GCD computations and exact divisions. The input is thus a non zero polynomial ''f'', and the first step of the algorithm consists in computing the GCD ''a''0 of ''f'' and its formal derivative ''f. If :$$ f = a_1 a_2^2 a_3^3 \cdots a_k^k is the desired factorization, we have thus :$$ a_0 = a_2^1 a_3^2 \cdots a_k^, :$$ f/a_0 = a_1 a_2 a_3 \cdots a_k and :$$ f'/a_0 = \sum_^k i a_i' a_1 \cdots a_ a_ \cdots a_k. If we set $b\_1=f/a\_0$, $c\_1=f\text{'}/a\_0$ and $d\_1=c\_1-b\_1\text{'}$, we get that :$$ \gcd(b_1,d_1) = a_1, :$$ b_2=b_1/a_1 = a_2 a_3 \cdots a_n, and :$$ c_2=d_1/a_1 = \sum_^k (i-1) a_i' a_2 \cdots a_ a_ \cdots a_k. Iterating this process until $b\_=1$ we find all the $a\_i.$ This is formalized into an algorithm as follows: The degree of $c\_i$ and $d\_i$ is one less than the degree of $b\_i.$ As $f$ is the product of the $b\_i,$ the sum of the degrees of the $b\_i$ is the degree of $f.$ As the complexity of GCD computations and divisions increase more than linearly with the degree, it follows that the total running time of the "repeat" loop is less than the running time of the first line of the algorithm, and that the total running time of Yun's algorithm is upper bounded by twice the time needed to compute the GCD of $f$ and $f\text{'}$ and the quotient of $f$ and $f\text{'}$ by their GCD. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Square-free polynomial」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.